/**
 * 需求：
 *  1. 创建一棵树
 *  2. 可以实现往树中添加新的节点
 *  3. 可以实现删除树中的某节点及其子节点
 *  4. 可以返回树的深度
 *  5. 可以遍历树中的所有节点
 *  6. 可以返回一个节点的父节点
 *  7. 可以返回一个节点下面的所有子节点
 *  8. 可以返回指定节点所在深度
 */

class Node {
  constructor(data = '', parent = -1, pos = 0) {
    this.data = data;
    this.parent = parent;
    this.pos = pos;
    this.children = [];
    this.deep = 0;
  }
}

const nodeCount = Symbol('nodeCount'); // 树中节点总量
const linkSize = Symbol('linkSize'); // 链表长度
const nodes = Symbol('nodes'); // 节点链表
const getLeafNode = Symbol('getLeafNode'); // 获取叶子节点函数
class OrderTree {
  /**
   * @param {Any} data 节点数据实例
   */
  constructor(data = '') {
    this[nodes] = [new Node(data, -1, 0)]; // 带有默认根节点的节点链表
    this[linkSize] = 1; // 链表长度
    this[nodeCount] = 1; // 节点数
    this.leafNode = []; // 叶子节点数组
    // this.deg = 1; // 树的度
    // this.deep = 1; // 树的深度
  }

  /* 获取叶子节点 */
  [getLeafNode]() {
    let leafNode = [];
    for (let j = 0; j < this[linkSize]; j++) {
      if (this[nodes][j] && this.children(this[nodes][j]).length === 0) {
        leafNode.push(this[nodes][j]);
      }
    }
    this.leafNode = leafNode;
  }

  /**
   * 按照指定参数类型返回符合条件的节点
   * @param {function | number} filter 
   * @return {Node | Array<Node>} 返回的节点或节点数组
   */
  getNode(filter) {
    if (typeof filter === 'string' || typeof filter === 'number') {
      if (typeof filter === 'string') { if (!/\d+/.test(filter)) { throw new Error('getNode 过滤参数只能是数字') } }
      filter = +filter;
      return this[nodes][filter];
    }
    if (typeof filter === 'function') {
      let result = [];
      for (let i = 0; i < this[linkSize]; i++) {
        if (filter(this[nodes][i])) result.push(this[nodes][i]);
      }
      if (result.length === 1) { return result[0]; }
      if (result.length === 0) { return null; }
      return result;
    }
    return this.getRoot();
  }

  /**
   * 向给入的父节点中添加子节点
   * @param {Any} data 新节点的数据实例
   * @param {number} parent 父级节点下标
   * @return {Node} 新添加的节点
   */
  addNode(data, parent = this.getRoot()) {
    let newNode = null;
    if (this[nodeCount] === this[linkSize]) { // 满链表
      let pos = this[nodes].length;
      newNode = new Node(data, parent.pos, pos);
      this[nodes].push(newNode);
      parent.children.push(this[nodes].length - 1);
      this[linkSize]++;
      this[nodeCount]++;
    } else { // 链表有空
      for (let i = 0; i < this[linkSize]; i++) {
        newNode = new Node(data, parent.pos, i);
        if (!this[nodes][i]) {
          this[nodes][i] = newNode;
          parent.children.push(i);
        }
      }
      this[nodeCount]++;
    }
    this[getLeafNode](); // 重构叶子节点数组
    return newNode;
  }

  /**
   * 删除指定实例或指定下标对应的实例
   * @param {Node | number} node 特定的节点实例或者实例下标
   */
  removeNode(node) {
    let trueNode = null;
    if (typeof node === 'number') trueNode = this[nodes][node];
    else trueNode = node;
    let children = this.children(trueNode);
    while (children.length > 0) { // 存在子节点
      for (let i = 0; i < children.length; i++) {
        this.removeNode(children[i]);
        children.splice(i, 1);
      }
    }
    for (let i = 0; i < this[linkSize]; i++) {
      if (this[nodes][i] && this[nodes][i] === trueNode) {
        let p = this[nodes][this[nodes][i].parent];
        p.children.splice(p.children.indexOf(this[nodes][i].pos), 1);
        this[nodes][i] = null;
        this[nodeCount]--;
      }
    }
    this[getLeafNode]();
  }

  /**
   * 删除指定节点，将要删除节点的子节点直接交给父亲节点
   * @param {Node} node 要删除的节点
   */
  singleRemove(node) {
    let parent = this[nodes][node.parent];
    for (let c = 0; c < node.children.length; c += 1) {
      let child = this[nodes][node.children[c]];
      if (child) {
        child.parent = node.parent;
        parent.children.push(node.children[c]);
      }
    }
    let index = parent.children.indexOf(node.pos);
    parent.children.splice(index, 1);
    this[nodes][node.pos] = false;
    this[nodeCount]--;
    this[getLeafNode]();
  }

  /* 返回根节点 */
  getRoot() { return this[nodes][0]; }

  /**
   * 返回指定节点的直接子节点列表
   * @param {Node} node 指定节点
   * @return {Array<Node>} 指定节点的子节点列表
   */
  children(node) {
    let children = [];
    for (let i = 0; i < this[linkSize]; i++) {
      if (this[nodes][i] && this[nodes][i].parent === node.pos) { // 子节点存在
        children.push(this[nodes][i]);
      }
    }
    return children;
  }

  /**
   * 返回树的深度或者指定节点所在深度
   * @param optional {Node} node 开始计算深度的节点
   */
  deep(node) {
    let max = 0;
    if (!node) {
      for (let i = 0; i < this.leafNode.length; i += 1) {
        let temp = this.leafNode[i], deep = 0;
        let p = temp.parent;
        while (p !== -1 && this[nodes][p]) {
          p = this[nodes][p].parent;
          deep++
        }
        if (deep > max) max = deep;
      }
    } else {
      let deep = 0, p = node.parent;
      while (p !== -1 && this[nodes][p]) {
        p = this[nodes][p].parent;
        deep++
      }
      if (deep > max) max = deep;
    }
    return max;
  }

  /* 返回可操作的数据数组 */
  getList() {
    let list = [];
    for (let i = 0; i < this[linkSize]; i++) {
      let temp = this[nodes][i]
      if (temp) {
        temp.deep = this.deep(temp);
        temp.data.styleStr = (function (node) {
          let result = [];
          for (let key in node.data.style) {
            result.push(`${key}:${node.data.style[key]}`);
          }
          return `${result.join(';')};`;
        })(temp)
        list.push(Object.assign({}, temp));
      } else list.push(false);
    }
    return list;
  }

  /* 提供从叶节点开始的向根节点遍历的递归方法 */
  leafToRoot(cb = () => { }) {
    let leaf = null;
    const visitParent = (node) => {
      if (node.parent !== -1) {
        let ancestor = this.getNode(node.parent);
        cb(leaf, node, ancestor);
        visitParent(ancestor);
      } else {
        cb(leaf, node, this.getRoot());
      }
    }

    for (let i = 0; i < this.leafNode.length; i += 1) {
      if (this.leafNode[i]) {
        leaf = this.leafNode[i];
        visitParent(this.leafNode[i]);
      }
    }
  }

  /**
   * 按层级（深度）遍历
   * @param {number} layer 要遍历的层级
   */
  traverseByDeep(layer = 0, cb = () => { }) {
    for (let i = 0; i < this[linkSize]; i += 1) {
      let temp = this[nodes][i];
      if (temp && this.deep(temp) === layer) {
        cb(temp);
      }
    }
  }

  /**
   * 普通全体遍历
   * @param {function} cb 回调
   */
  traverse(cb = () => { }) {
    for (let i = 0; i < this[linkSize]; i += 1) {
      cb(this[nodes][i]);
    }
  }
}

module.exports = OrderTree;